package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printInorder

/**
 * https://leetcode.cn/problems/delete-node-in-a-bst/description/
 * https://programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.htm
 *
 * 450. 删除二叉搜索树中的节点
 *
 * 示例 1:
 * 输入：root = [5,3,6,2,4,null,7], key = 3
 * 输出：[5,4,6,2,null,null,7]
 *
 * 示例 2:
 * 输入: root = [5,3,6,2,4,null,7], key = 0
 * 输出: [5,3,6,2,4,null,7]
 *
 * 示例 3:
 * 输入: root = [], key = 0
 * 输出: []
 */
class leetcode_450 {
    @Test
    fun test_1() {
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)
        val root = n5
        root.left = n3
        root.right = n6
        n3.left = n2
        n3.right = n4
        n6.right = n7

        val result = deleteNode(root, 3)
        val actual = printInorder(result)
        val expect = arrayListOf(2, 4, 5, 6, 7)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)
        val root = n5
        root.left = n3
        root.right = n6
        n3.left = n2
        n3.right = n4
        n6.right = n7

        val result = deleteNode(root, 0)
        val actual = printInorder(result)
        val expect = arrayListOf(2, 3, 4, 5, 6, 7)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_3() {
        // 测试左空右空
        val result = deleteNode(null, 0)
        val actual = printInorder(result)
        val expect = ArrayList<Int>()
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_more_test_1() {
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)

        val root = n5
        root.left = n3
        root.right = n6
        n3.left = n2
        n3.right = n4
        n6.right = n7

        // 测试左空右空
        val result = deleteNode(root, 2)
        val actual = printInorder(result)
        val expect = arrayListOf(3, 4, 5, 6, 7)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_more_test_2() {
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)

        val root = n5
        root.left = n3
        root.right = n6
        n3.left = n2
        n3.right = n4
        n6.right = n7
        // 测试左空右空
        val result = deleteNode(root, 4)
        val actual = printInorder(result)
        val expect = arrayListOf(2, 3, 5, 6, 7)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_more_test_3() {
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n8 = TreeNode(8)
        val n9 = TreeNode(9)

        val root = n5
        root.left = n3
        root.right = n6
        n3.left = n2
        n3.right = n4
        n6.right = n9
        n9.left = n8

        // 测试左非空右空
        val result = deleteNode(root, 9)
        val actual = printInorder(result)
        val expect = arrayListOf(2, 3, 4, 5, 6, 8)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_more_test_4() {
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n9 = TreeNode(9)
        val n10 = TreeNode(10)

        val root = n5
        root.left = n3
        root.right = n6
        n3.left = n2
        n3.right = n4
        n6.right = n9
        n9.left = n10

        // 测试左空右非空
        val result = deleteNode(root, 9)
        val actual = printInorder(result)
        val expect = arrayListOf(2, 3, 4, 5, 6, 10)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_more_test_5() {
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n8 = TreeNode(8)
        val n9 = TreeNode(9)
        val n10 = TreeNode(10)
        val n15 = TreeNode(15)

        val root = n5
        root.left = n3
        root.right = n6
        n3.left = n2
        n3.right = n4
        n5.right = n8
        n8.left = n6
        n8.right = n10
        n10.left = n9
        n10.right = n15


        // 测试左非空右非空
        Assert.assertEquals(arrayListOf(2, 3, 4, 5, 6, 8, 9, 10, 15).toString(), printInorder(root).toString())
        val result = deleteNode(root, 8)
        val actual = printInorder(result)
        val expect = arrayListOf(2, 3, 4, 5, 6, 9, 10, 15)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_more_test_6() {
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)

        val root = n5
        root.left = n3
        root.right = n6
        n3.left = n2
        n3.right = n4
        n5.right = n6
        n6.right = n7

        // 测试左非空右非空
        Assert.assertEquals(arrayListOf(2, 3, 4, 5, 6, 7).toString(), printInorder(root).toString())
        val result = deleteNode(root, 3)
        val actual = printInorder(result)
        val expect = arrayListOf(2, 4, 5, 6, 7)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_more_test_7() {
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)

        val root = n5
        root.left = n3
        root.right = n6
        n3.left = n2
        n3.right = n4
        n5.right = n6
        n6.right = n7

        // 测试左非空右非空 - 删除头
        Assert.assertEquals(arrayListOf(2, 3, 4, 5, 6, 7).toString(), printInorder(root).toString())
        val result = deleteNode(root, 5)
        val actual = printInorder(result)
        val expect = arrayListOf(2, 3, 4, 6, 7)
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    fun deleteNode(root: TreeNode?, key: Int): TreeNode? {
        /*
        1 不用考虑用什么遍历方法，根据大小方向遍历
        2 删除的结果？

        #1 没有找到
        找到了要删除的叶子节点，分几种情况
        #2 左空右空，返回null。 E.g., 删除2，删除4
        #3 左不空右空，返回左
        #4 左空右不空，返回右。E.g., 删除示例1-7
        #5 左不空右不空 （最复杂） 。E.g., 删除示9
         方法1：左孩子继位
         方法2：右孩子继位。找到右孩子中大小仅次于删除节点的节点p
         同时把删除节点的左孩子设置成p的左孩子
         返回节点p

                    5
                3         6
             2    4           9
                           8      20
                               19    22

         */
        // 递归
        // T - LogN
        // S - LogN

        // 终止条件
        // #1 没有找到
        if (null == root) {
            return null
        }

        if (root.`val` > key) {
            // 向左
            root.left = deleteNode(root.left, key)
        } else if (root.`val` < key) {
            // 向右
            root.right = deleteNode(root.right, key)
        } else { // root.`val` == key
            // #2 左空右空
            if (null == root.left && null == root.right) {
                return null
            }
            // #3 左不空右空
            if (null != root.left && null == root.right) {
                return root.left
            }

            // #4 左空右不空
            if (null == root.left && null != root.right) {
                return root.right
            }

            // #5 左不空右不空，比如删除
            // 若左右子树均不为空，我们有两种选择：
            //从「当前节点的左子树」中选择「值最大」的节点替代 root 的位置，确保替代后仍满足 BST 特性；5,2,6,null,4,null,7
            var p: TreeNode = root.left!!
            while (p.right != null) {
                p = p.right!!
            }
            // 将删除节点root的左孩子作为p左孩子
            p.right = root.right // 8 变成19的左孩子
            // 将删除节点root的右孩子作为右孩子返回 20
            return root.left

            //从「当前节点的右子树」中选择「值最小」的节点替代 root 的位置，确保替代后仍满足 BST 特性；(本题答案) ： [5,4,6,2,null,null,7]
            // 找到删除节点root的右孩子的次小节点 p  => 19
//            var p: TreeNode = root.right!!
//            while (p.left != null) {
//                p = p.left!!
//            }
//            // 将删除节点root的左孩子作为p左孩子
//            p.left = root.left // 8 变成19的左孩子
//            // 将删除节点root的右孩子作为右孩子返回 20
//            return root.right
        }
        return root
    }
}